1、有序数组中 查找某个指定数字的个数
思想：看见有序，应该第一时间想到二分查找，找到数后，得判断其左右边是不是一样得。
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size()==0)
        {
            return 0;
        }
        int left=0;
        int right=nums.size()-1;
        int mid=0;
        int count=0;
        while(left<=right)
        {
            mid=(left+right)/2;

            if(nums[mid]>target)
            {
                right=mid-1;
            }
            else if(nums[mid]<target)
            {
                left=mid+1;
            }
            else if(nums[mid]==target)
            {
                int i=mid-1;
                int j=mid+1;
                count++;
                while(i>=left&&nums[i]==target)
                {
                    i--;
                    count++;
                }
                while(j<=right&&nums[j]==target)
                {
                    j++;
                    count++;
                }
                return count;
            }
        }
        return count;
    }
};

2、复杂链表的复制
思想：
第一步：从头结点开始，复制节点，并且连接在其后面，
第二步：按照头结点的random指向，来将复制节点的random指向连接起来
第三步：删除掉原链表和复制链表的相连
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL)
        {
            return NULL;
        }
        Node* cur=head;
        Node* tail=cur;
        Node* root=NULL;
        //将新建节点与原节点相连
        while(tail)
        {
            tail=cur->next;
            Node* copy=(Node*)malloc(sizeof(Node));
            copy->val=cur->val;
            copy->next=tail;
            cur->next=copy;
            cur=tail;
        }
        root=head->next;
        Node* cur1=head;
        Node* copy1=root;
        //将复制链表的random连接起来
        while(cur1)
        {
            if(cur1->random)
                copy1->random=cur1->random->next;
            else
                copy1->random=NULL;
            cur1=copy1->next;
            if(cur1)
                copy1=cur1->next;
        }
        //断
        Node* cur2=head;
        Node* copy2=root;
        Node* tail2=head;

        while(tail2)
        {
            tail2=copy2->next;
            cur2->next=tail2;
            if(tail2)
                copy2->next=tail2->next;
            else
                copy2->next=NULL;
            cur2=tail2;
            if(tail2)
                copy2=tail2->next;
        }
        return root;
    }
};

3、左旋转字符串；就是将字符串的前n位旋转到字符串的尾部
思想：2个for循环，利用尾插法   分别将数据插到s中
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string s1;
        for(int i=n;i<s.size();++i)
        {
            s1.push_back(s[i]);
        }
        for(int i=0;i<n;i++)
        {
            s1.push_back(s[i]);
        }
        return s1;
    }
};

4、求出一颗二叉树的镜像树
思想：递归，将根节点的左右子树对换，然后依次右左子树，右子树来对换
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr)
        {
            return nullptr;
        }
        TreeNode* tmp=root->left;
        root->left=root->right;
        root->right=tmp;
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

